1. $T$ : Type
\\[0ex]2. $L_{1}$ : $T$ List
\\[0ex]3. $L_{2}$ : $T$ List
\\[0ex]4. $L$ : $T$ List
\\[0ex]5. $x$ : $T$
\\[0ex]6. $\forall$$i$, $j$:$\mathbb{N}$. ($i$ $<$ $\parallel$$L$$\parallel$) $\Rightarrow$ ($j$ $<$ $\parallel$$L$$\parallel$) $\Rightarrow$ ($\neg$($i$ = $j$)) $\Rightarrow$ ($\neg$($L$[$i$] = $L$[$j$]))
\\[0ex]7. $f_{1}$ : \{0..$\parallel$$L_{1}$ @ [$x$]$\parallel^{-}$\}$\rightarrow$\{0..$\parallel$$L$$\parallel^{-}$\}
\\[0ex]8. increasing($f_{1}$;$\parallel$$L_{1}$ @ [$x$]$\parallel$)
\\[0ex]9. $\forall$$j$:\{0..$\parallel$$L_{1}$ @ [$x$]$\parallel^{-}$\}. ($L_{1}$ @ [$x$])[$j$] = $L$[($f_{1}$($j$))]
\\[0ex]10. $f$ : \{0..($\parallel$$L_{2}$$\parallel$+1)$^{-}$\}$\rightarrow$\{0..$\parallel$$L$$\parallel^{-}$\}
\\[0ex]11. increasing($f$;$\parallel$$L_{2}$$\parallel$+1)
\\[0ex]12. $\forall$$j$:\{0..($\parallel$$L_{2}$$\parallel$+1)$^{-}$\}. [$x$ / $L_{2}$][$j$] = $L$[($f$($j$))]
\\[0ex]13. $\parallel$$L_{1}$ @ [$x$ / $L_{2}$]$\parallel$ = $\parallel$$L_{1}$$\parallel$+$\parallel$$L_{2}$$\parallel$+1
\\[0ex]14. $\parallel$[]$\parallel$ $\geq$ 0 
\\[0ex]$\vdash$  increasing($\lambda$$i$.if $i$ $\leq$z $\parallel$$L_{1}$$\parallel$ then $f_{1}$($i$) else $f$($i$ {-} $\parallel$$L_{1}$$\parallel$) fi ;$\parallel$$L_{1}$ @ [$x$ / $L_{2}$]$\parallel$)